翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

dominating set : ウィキペディア英語版
dominating set

In graph theory, a dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' of ''V'' such that every vertex not in ''D'' is adjacent to at least one member of ''D''. The domination number γ(''G'') is the number of vertices in a smallest dominating set for ''G''.
The dominating set problem concerns testing whether γ(''G'') ≤ ''K'' for a given graph ''G'' and input ''K''; it is a classical NP-complete decision problem in computational complexity theory . Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.
Figures (a)–(c) on the right show three examples of dominating sets for a graph. In each example, each white vertex is adjacent to at least one red vertex, and it is said that the white vertex is ''dominated'' by the red vertex. The domination number of this graph is 2: the examples (b) and (c) show that there is a dominating set with 2 vertices, and it can be checked that there is no dominating set with only 1 vertex for this graph.
==History==

As note, the domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. Their bibliography lists over 300 papers related to domination in graphs.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「dominating set」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.